\begin{Exercise}[title={冒泡排序},difficulty=1]
\label{ex:bubble}
\Question\label{ex:bubble q1} 编写一个针对~int 类型的~slice 冒泡排序的函数。这里 \cite{bubblesort}：
\begin{quote}
它在一个列表上重复步骤来排序，比较每个相邻的元素，并且顺序错误的时候，交换它们。
一遍一遍扫描列表，直到没有交换为止，这意味着列表排序完成。
算法得名于更小的元素就像``泡泡''一样冒到列表的顶端。
\end{quote}

\cite{bubblesort} 这里有一个过程代码作为示例：
\begin{lstlisting}[language=pascal]
procedure bubbleSort( A : list of sortable items )
  do
    swapped = false
    for each i in 1 to length(A) - 1 inclusive do:
      if A[i-1] > A[i] then
        swap( A[i-1], A[i] )
        swapped = true
      end if
    end for
  while swapped
end procedure
\end{lstlisting}
\end{Exercise}

\begin{Answer}
\Question 
冒泡排序并不是最有效率的，对于~$n$ 个元素它的算法复杂度是~$O(n^2)$。
快速排序~\cite{quicksort} 是更好的排序算法。

但是冒泡排序容易实现。
\lstinputlisting[caption=冒泡排序,linerange=4-19]{ex-functions/src/bubblesort.go}

由于~slice 是一个引用类型，\func{bubblesort} 函数可以工作，并且无须返回排序后的~slice。
\end{Answer}
